package com.jack.leetcode.每日一题;

/*** 
 * @author zhangjie
 * @date 2020/4/12 19:39
 */
public class 交点 {

    public static void main(String[] args) {
        int[] s1 = {0, 0};
        int[] e1 = {1, 0};
        int[] s2 = {1, 1};
        int[] e2 = {0, -1};
        double[] result = intersection(s1, e1, s2, e2);
        for (int i = 0; i < 2; i++) {
            System.out.println(result[i]);
        }

        int[] s11 = {0, 0};
        int[] e11 = {1, 1};
        int[] s21 = {1, 0};
        int[] e21 = {2, 1};
        double[] result1 = intersection(s11, e11, s21, e21);
        for (int i = 0; i < 2; i++) {
            System.out.println(result1[i]);
        }

        int[] s12 = {0, 0};
        int[] e12 = {3, 3};
        int[] s22 = {1, 1};
        int[] e22 = {2, 2};
        double[] result2 = intersection(s12, e12, s22, e22);
        for (int i = 0; i < 2; i++) {
            System.out.println(result2[i]);
        }
    }

    public static double[] intersection(int[] start1, int[] end1, int[] start2, int[] end2) {
        double[] result = new double[2];
        int x11 = start1[0]>end1[0]?end1[0]:start1[0], y11 = start1[1]>end1[1]?end1[1]:start1[1],
                x12 = start1[0]<=end1[0]?end1[0]:start1[0], y12 = start1[1]<=end1[1]?end1[1]:start1[1];
        int x21 = start2[0]>end2[0]?end2[0]:start2[0], y21 = start2[1]>end2[1]?end2[1]:start2[1],
                x22 = start2[0]<=end2[0]?end2[0]:start2[0], y22 = start2[1]<=end2[1]?end2[1]:start2[1];
        int minx = x11 < x12 ? x11 : x12;
        int maxx = x21 < x22 ? x22 : x21;
        int miny = y11 < y12 ? y11 : y12;
        int maxy = y21 < y22 ? y22 : y21;
        if (x12 - x11 == 0 && x22 - x21 == 0) {
            int miny2 = y21 < y22 ? y21 : y21;
            if (x11 == x21 && miny >= miny2) {
                result[0] = 0;
                result[1] = y11 < y21 ? y21 : y11;
                return result;
            } else {
                return new double[0];
            }
        }
        if (x12 - x11 == 0) {
            int k2 = (y22 - y21) / (x22 - x21);
            int b2 = y21 - k2 * x21;
            if (x21 <= 0 && x22 >= 0) {
                result[0] = 0.0;
                result[1] = b2;
                return result;
            } else {
                return new double[0];
            }
        }
        if (x22 - x21 == 0) {
            int k1 = (y12 - y11) / (x12 - x11);
            int b1 = y11 - k1 * x11;
            if (x11 <= 0 && x12 >= 0) {
                result[0] = 0.0;
                result[1] = b1;
                return result;
            } else {
                return new double[0];
            }
        }

        int k1 = (y12 - y11) / (x12 - x11);
        int k2 = (y22 - y21) / (x22 - x21);
        int b1 = y11 - k1 * x11;
        int b2 = y21 - k2 * x21;
        if (k1 == k2) {
            if (b1 != b2) {
                return new double[0];
            } else {
                if (x12 >= x21 && x12 <= x22 && y12 >= y21 && y12 <= y22) {
                    result[0] = x11 < x21 ? x21 : x11;
                    result[1] = y11 < y21 ? y21 : y11;
                    return result;
                }else{
                    return new double[0];
                }
            }
        }
        result[0] = (b1 - b2 + 0.0) / (k2 - k1);
        result[1] = k1 * result[0] + b1;
        if (result[0] >= minx && result[0] <= maxx &&
                result[1] >= miny && result[1] <= maxy) {
            return result;
        } else {
            return new double[0];
        }
    }
}


//class Solution {
//    public double[] intersection(int[] start1, int[] end1, int[] start2, int[] end2) {
//        int x1 = start1[0], y1 = start1[1];
//        int x2 = end1[0], y2 = end1[1];
//        int x3 = start2[0], y3 = start2[1];
//        int x4 = end2[0], y4 = end2[1];
//
//        double[] ans = new double[2];
//        Arrays.fill(ans, Double.MAX_VALUE);
//        // 判断两直线是否平行
//        if ((y4-y3)*(x2-x1) == (y2-y1)*(x4-x3)) {
//            // 判断两直线是否重叠
//            if ((y2-y1)*(x3-x1) == (y3-y1)*(x2-x1)) {
//                // 判断 (x3, y3) 是否在「线段」(x1, y1)~(x2, y2) 上
//                if (isInside(x1, y1, x2, y2, x3, y3)) {
//                    updateRes(ans, x3, y3);
//                }
//                // 判断 (x4, y4) 是否在「线段」(x1, y1)~(x2, y2) 上
//                if (isInside(x1, y1, x2, y2, x4, y4)) {
//                    updateRes(ans, (double)x4, (double)y4);
//                }
//                // 判断 (x1, y1) 是否在「线段」(x3, y3)~(x4, y4) 上
//                if (isInside(x3, y3, x4, y4, x1, y1)) {
//                    updateRes(ans, (double)x1, (double)y1);
//                }
//                // 判断 (x2, y2) 是否在「线段」(x3, y3)~(x4, y4) 上
//                if (isInside(x3, y3, x4, y4, x2, y2)) {
//                    updateRes(ans, (double)x2, (double)y2);
//                }
//            }
//        } else {
//            // 联立方程得到 t1 和 t2 的值
//            double t1 = (double)(x3 * (y4 - y3) + y1 * (x4 - x3) - y3 * (x4 - x3) - x1 * (y4 - y3)) / ((x2 - x1) * (y4 - y3) - (x4 - x3) * (y2 - y1));
//            double t2 = (double)(x1 * (y2 - y1) + y3 * (x2 - x1) - y1 * (x2 - x1) - x3 * (y2 - y1)) / ((x4 - x3) * (y2 - y1) - (x2 - x1) * (y4 - y3));
//            // 判断 t1 和 t2 是否均在 [0, 1] 之间
//            if (t1 >= 0.0 && t1 <= 1.0 && t2 >= 0.0 && t2 <= 1.0) {
//                ans[0] = x1 + t1 * (x2 - x1);
//                ans[1] = y1 + t1 * (y2 - y1);
//            }
//        }
//        if (ans[0] == Double.MAX_VALUE) {
//            return new double[0];
//        }
//        return ans;
//    }
//
//    // 判断 (x, y) 是否在「线段」(x1, y1)~(x2, y2) 上
//    // 这里的前提是 (x, y) 一定在「直线」(x1, y1)~(x2, y2) 上
//    private boolean isInside(int x1, int y1, int x2, int y2, int x, int y) {
//        // 若与 x 轴平行，只需要判断 x 的部分
//        // 若与 y 轴平行，只需要判断 y 的部分
//        // 若为普通线段，则都要判断
//        return (x1 == x2 || (Math.min(x1, x2) <= x && x <= Math.max(x1, x2)))
//                && (y1 == y2 || (Math.min(y1, y2) <= y && y <= Math.max(y1, y2)));
//    }
//
//    private void updateRes(double[] ans, double x, double y) {
//        if (x < ans[0] || (x == ans[0] && y < ans[1])) {
//            ans[0] = x;
//            ans[1] = y;
//        }
//    }
//}
